package com.cty._03_SolutionSeekingMindset._35_CopyComplexList;

/**
 * @Auther: cty
 * @Date: 2020/7/13 11:33
 * @Description: 面试题35：复杂链表的复制
 * 题目：请实现函数ComplexListNode* Clone(ComplexListNode* pHead)，复
 * 制一个复杂链表。在复杂链表中，每个结点除了有一个m_pNext指针指向下一个
 * 结点外，还有一个m_pSibling 指向链表中的任意结点或者nullptr。
 * @version: 1.0
 */
public class CopyComplexList {

    // 克隆复杂链表
    public static ComplexListNode copyList(ComplexListNode listHead){
        listHead = cloneNodes(listHead);
        connectSiblingNodes(listHead);
        return reconnectNodes(listHead);
    }

    // 沿next方向clone节点
    private static ComplexListNode cloneNodes(ComplexListNode listHead){
        ComplexListNode current = listHead;
        while(current != null){
            ComplexListNode temp = new ComplexListNode(current.value);
            temp.next = current.next;
            current.next = temp;

            current = temp.next;
        }
        return listHead;
    }  // end ComplexListNode()

    // 连接sibling节点
    private static void connectSiblingNodes(ComplexListNode listHead){
        ComplexListNode current = listHead;
        while(current != null){
            ComplexListNode cloneNode = current.next;
            if(current.sibling != null)
                cloneNode.sibling = current.sibling.next;

            current = cloneNode.next;
        }  // end while
    }  // end connectSiblingNodes()

    // 将链表拆分
    private static ComplexListNode reconnectNodes(ComplexListNode listHead){
        ComplexListNode current = listHead;
        ComplexListNode cloneListHead = null;
        ComplexListNode cloneCurrent = null;

        if(current != null){
            cloneListHead = cloneCurrent = current.next;

            current.next = cloneCurrent.next;
            current = current.next;
        }

        while(current != null){
            cloneCurrent.next = current.next;
            cloneCurrent = cloneCurrent.next;

            current.next = cloneCurrent.next;
            current = current.next;
        }  // end while
        return cloneListHead;
    }  // end reconnectNodes()

}  // end class

class ComplexListNode{
    int value;
    ComplexListNode next;
    ComplexListNode sibling;

    public ComplexListNode(){}

    public ComplexListNode(int value){this.value = value;}
}
